Thực đơn
Kí pháp Ba Lan Cây biểu diễn biểu thứcDùng cây biểu diễn biểu thức có thể thấy rõ trình tự tính toán biểu thức.
Ví dụ:
a * (b + c) - d ^ 5Được thực hiện theo sơ đồ biểu diễn bởi cây nhi phân sau
- / \ * ^/ \ / \a + d 5 / \ b c
Ta mô tả quá trình đọc, ghi nhận giá trị và thực hiện phép tính, giống như quá trình duyệt cây biểu thức theo thứ tự giữa như sau:
Để đơn giản ta giả sử các phép toán đều là hai ngôi. Khi đó cây biểu thức là cây nhị phân đầy đủ. Quy tắc thực hiện phép toán trên cây như sau:
- - / \ / \ * ^ + ^ / \ / \ / \ / \a + d 5 * c d 5 / \ / \ b c a ba * b + c - 4 * d ^ 5 (1)
Theo cách này, mỗi khi duyệt một đỉnh
Khi duyệt theo thứ tự sau, việc thực hiện phép tính tiến hành theo quy tắc:
Mỗi khi thăm một đỉnh thì:
Với dãy (1) nếu không dùng đến dấu ngoặc, có thể có hai cây biểu thức khác nhau cho cùng một dãy đỉnh khi duyệt thứ tự giữa. Còn với dãy (2) cùng với lưu ý rằng các biến và hằng luôn được biểu diễn bằng các lá, các toán tử luôn biểu diễn bởi các nút trong, từ mỗi dãy dạng (2) ta luôn dựng lại được cây biểu thức duy nhất theo giải thuật sau:Khi độ dài dãy lớn hơn 1, duyệt từ bên trái sang, nếu gặp một phần tử là toán tử, thì lấy hai phần tử đứng trước nó ra khỏi dãy chuyển thành hai con của phần tử ấy (theo đúng thứ tự).Vì thế biểu thức viết bởi dãy (2) là hoàn toàn xác định.
Thực đơn
Kí pháp Ba Lan Cây biểu diễn biểu thứcLiên quan
Kí Kích cỡ dương vật người Kính vạn hoa (truyện) Kính mắt Kính thiên văn Chân trời sự kiện Kính hiển vi điện tử truyền qua Kính viễn vọng Kính ngữ tiếng Nhật Kính vạn hoa (phim truyền hình) Kính viễn vọng không gian HubbleTài liệu tham khảo
WikiPedia: Kí pháp Ba Lan